# 算法思想：运用kd树，将所有样本点划分至小区域中，每个区域有<2k个实例
# 对于一个测试点，首先找到其对应的区域，找出区域中第k远样本点，然后以此距离去更新最近k个点，直到递归到根节点
# 如果以该距离为半径，测试点为球心的球体与其他区域有交点，则去该区域的点中尝试更新，直到只剩下k个点，且所有涉及区域的点都遍历过

# author@bupt_kt
# date@08/31/2021
# 由于水平有限，暂时想不出构建kd树的最优算法，暂时采用求解最近k来学习

import numpy as np
from operator import itemgetter

##读取训练集数据
def input_data():
    data=[]
    label=[] ##创建标签数组，为每一项数据做标记
    file=open(r'Mnist/mnist_train.csv','r')
    for line in file.readlines():
        l=line.strip().split(',')
        label.append(l[0])
        data.append([int(num) for num in l[1:]])    ##这里的数据特指数据集中的x
    return data,label

##进行模型训练
def training(data,label,k):## k近邻没有显式的学习过程，因此直接测试准确率
    data=np.mat(data)  ##将数据集转化为矩阵，方便后续运算
    m,n=np.shape(data) ##获得数据集的行列数
    file = open(r'Mnist/mnist_test.csv', 'r')
    error = 0
    data2 = []
    label2 = []
    dist=[]
    for lines in file.readlines(): ##读取测试集
        l = lines.strip().split(',')
        label2.append(l[0])
        data2.append([int(num) for num in l[1:]])
    data2 = np.mat(data2)
    number,number2 = np.shape(data2)

    for i in range(100): ##开始测试
        for j in range(m): ##求到所有样例点的距离，保存到样例点的距离，样例点的值，使得之后的排序不会失去原来的数组下标信息
            dist.append([np.sqrt(np.sum(np.square(data2[i]-data[j]))),j,label[j]])
        dist=sorted(dist,key=itemgetter(0))## 以距离排序

        count=[] ##投票计数
        for j in range(k):
            count.append(dist[j][2])
        temp=0
        temp2=0
        for j in range(k):
            if temp<count.count(count[j]):
                temp=count.count(count[j])
                temp2=count[j]

        if temp2!=label2[i]:
            error+=1
        dist.clear()

    print(1-error/number)

    return




if __name__ == '__main__':
    data,label=input_data()
    training(data,label,20)
